package sort;

import java.util.Arrays;

/**
 * 插入排序
 *
 * @author shkstart
 * @create 2021-04-30 14:14
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = {122, 12, 61, 34, 90};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void insertSort(int[] arr) {
        for (int i = 1; i <arr.length ; i++) {
            //定义当前元素 和 当前元素的上一个元素的索引
            int s1 = arr[i];
            int index = i - 1;
            while (index >= 0 && s1 < arr[index]) {
//        如果当前元素小于 它上一个元素 就交换
//            先把上一个元素赋给当前元素的索引
                arr[index + 1] = arr[index];
                index--;  //减减的目的是让当前元素跟上一轮比过的元素进行比较
            }
//        在把s1的值赋值给上一个元素的索引
            arr[index + 1] = s1;

            System.out.println("第"+ i +" 轮");
            System.out.println(Arrays.toString(arr));

            /**
             * 第1 轮
             * [12, 122, 61, 34, 90]
             * 第2 轮
             * [12, 61, 122, 34, 90]
             * 第3 轮
             * [12, 34, 61, 122, 90]
             * 第4 轮
             * [12, 34, 61, 90, 122]
             */
        }


    }
}
